package algorithm.array;

import java.util.Arrays;

/**
 * @Author: Hevery
 * @Description:
 * @Date: Created on 2017/10/3
 * @Modified By:
 */
public class MaxSubArray {
    public static void main(String[] args) {
        int []A = new int[]{-3,-1,-3,-1};
        System.out.println(maxSubArray(A));
        System.out.println(maxSum(A));
        System.out.println(maxSubArrayOrigin(A));
        int[] record = maxSubSequenceOfArray(A);
        for (int i = 0; i < record.length; i++) {
            System.out.print(record[i] + " ");
        }
    }
    public static int maxSubArrayOrigin(int[] A){
        int[] record = new int[A.length];
        if(A == null || A.length == 0){
            return 0;
        }
        int cur = 0;
        for (int i = 0; i < A.length; i++) {
            cur = Math.max(A[i], cur + A[i]);
            record[i] = cur;
        }
        for (int i = 0; i < record.length; i++) {
            System.out.print(record[i] + " ");
        }
        System.out.println();
        Arrays.sort(record);
       return record[record.length-1];
    }
    public static int maxSubArray(int []A){
        if(A == null || A.length == 0){
            return 0;
        }
        int max = A[0],currMax = A[0],maxIndex = 0;
        for (int i = 1; i < A.length; i++) {
            currMax = Math.max(A[i],currMax + A[i]);
            max = Math.max(max, currMax);
        }
        return max;
    }
    public static int maxSum(int[] A){
        if(A == null || A.length == 0){
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0; i < A.length; i++) {
            cur += A[i];
            max = Math.max(max, cur);
            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }

    public static int[] maxSubSequenceOfArray(int[] A){

        if(A == null || A.length == 0){
            return null;
        }
        int curSum = 0, maxSum = Integer.MIN_VALUE;
        int start = 0, end = 0 ,endOld = 0;
        for (int i = 0; i < A.length; i++) {
            if(curSum <= 0){
                curSum = A[i];
                start = i;
            }else{
                curSum +=A[i];
                endOld = i;
            }
            if(curSum >= maxSum){
                maxSum = curSum;
                end = i;
            }
        }
        int index = 0;
        int[] record = new int[end - start + 1];
        for (int i = start; i <= end; i++) {
            record[index++] = A[i];
        }
        return record;
    }
}
